/*!
 * \file bitmap.h
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Macros and inline functions for bitwise operations on bitmaps using bit-parallelism.
 *
 * A bitmap is an array of bits to represent sets in which a bit of index \c i represents element \c i of the set. For a bitmap \c B,
 * \c B[\c i] \c = \c 1 means that element \c i is in the set; otherwise, \c i is not.
 *
 * Bitmaps are defined as arrays of three different types depending on the number of bits per node, namely: \c unsigned \c char (8 bits
 * per node), \c unsigned \c long \c int (32 bits per node), and \c unsigned \c long \c long \c int (64 bits per node). The type
 * currently in use is selected by means of the definition of a macro name, respectively with \c -D_ARCH8_, \c -D_ARCH32_, or
 * \c -D_ARCH64_, in the \c gcc command line.
 */

#ifndef BITMAP_H_
#define BITMAP_H_

#include <stdlib.h>

#ifdef _SSE_
#include <smmintrin.h> // SSE4

/* align_size has to be a power of two !! */
static inline void *aligned_malloc(size_t size) {
	char *ptr = (char *)malloc(size + 16 + sizeof(char *));

	if (ptr==NULL)
		return(NULL);

	printf("ptr=%d\n", (int) ptr);

	char * aligned_ptr = ptr + sizeof(char *) + (16 - (((int) (ptr + sizeof(char *))) & 0xF));
	*(((char **) aligned_ptr)-1) = ptr;

	printf("aligned_ptr=%d\n", (int) aligned_ptr);

	printf("saved=%d at %d\n", (int) *(((char **) aligned_ptr)-1), (int) (((char **) aligned_ptr)-1));

	return aligned_ptr;
}

static inline void aligned_free(void *ptr) {
	printf("to be free'd=%d at %d\n", (int) *(((char **) ptr)-1), (int) (((char **) ptr)-1));
	fflush(NULL);

	free(*(((char **) ptr)-1));
}
#endif

#include <stddef.h>
#include <stdio.h>
#include <string.h>

#ifdef _ARCH32_  // see comments at #ifdef _ARCH8_
typedef unsigned long int NODETYPE; //!< Bitmap node's type
#define BSIZE 32					//!< Number of bits in a node
#define WSIZE 4						//!< Number of bytes in a node
#define LOGB 5L						//!< Logarithmic of BSIZE
#define LOGW 2L						//!< Logarithmic of WSIZE
#define LOGBW 7L					//!< LOGB \c + LOGW
#define ONE 1L						//!< Node set to \c 1
#define NODEMAX 0xFFFFFFFF			//!< Node's maximum value
#define MASKB 0x1FL					//!< Mask used to select the LOGB least significant bits
//#define MASKB 0xFFFFFFE0

#define MASKSZ 33					//!< Number of elements in __mask
static const NODETYPE __mask[MASKSZ] = {
	0xFFFFFFFF,
	0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, 0xFFFFFFF0,
	0xFFFFFFE0, 0xFFFFFFC0, 0xFFFFFF80, 0xFFFFFF00,
	0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, 0xFFFFF000,
	0xFFFFE000, 0xFFFFC000, 0xFFFF8000, 0xFFFF0000,
	0xFFFE0000, 0xFFFC0000, 0xFFF80000, 0xFFF00000,
	0xFFE00000, 0xFFC00000, 0xFF800000, 0xFF000000,
	0xFE000000, 0xFC000000, 0xF8000000, 0xF0000000,
	0xE0000000, 0xC0000000, 0x80000000, 0x00000000
};

#define NODECOUNTER(i) __builtin_popcountl(i)
#define NODELEAST(w) (__builtin_ffsl(w)-1)
#define NODENEXTLEAST(w, i) (__builtin_ffsl((w) & __mask[i + 1])-1)
#define NODEMOST(i) (BSIZE-__builtin_clzl(i)-1)
#define NODEPREVMOST(w, i) (BSIZE-__builtin_clzl((w) & ~__mask[i])-1)

#elif _ARCH64_

typedef unsigned long long int NODETYPE; //!< bitmap node's type
#define BSIZE 64
#define WSIZE 8
#define LOGB 6LL
#define LOGW 3
#define LOGBW 9

#define ONE 1LL
#define NODEMAX 0xFFFFFFFFFFFFFFFF
#define MASKB 0x3FLL
//#define MASKB 0xFFFFFFFFFFFFFFC0

#define MASKSZ 65
static const NODETYPE __mask[MASKSZ] = {
	0xFFFFFFFFFFFFFFFF,
	0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0,
	0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00,
	0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000,
	0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000,
	0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000,
	0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000,
	0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000,
	0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000,
	0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000,
	0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000,
	0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000,
	0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000,
	0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000,
	0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000,
	0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000,
	0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000
};

#define NODECOUNTER(i) __builtin_popcountll(i)
#define NODELEAST(w) (__builtin_ffsll(w)-1)
#define NODENEXTLEAST(w, i) (__builtin_ffsll((w) & __mask[i + 1])-1)
#define NODEMOST(i) (BSIZE-__builtin_clzll(i)-1)
#define NODEPREVMOST(w, i) (BSIZE-__builtin_clzll((w) & ~__mask[i])-1)

#else
/*! \typedef NODETYPE
 * \brief Bitmap node's type
 *
 */
typedef unsigned char NODETYPE; //!< Bitmap node's type
#define BSIZE 8								//!< Number of bits in a node
#define WSIZE 1								//!< Number of bytes in a node
#define LOGB 3								//!< Logarithmic of BSIZE
#define LOGW 0								//!< Logarithmic of WSIZE
#define LOGBW 3								//!< LOGB \c + LOGW
#define ONE 1								//!< Node set to \c 1
#define NODEMAX 0xFF						//!< Node's maximum value
#define MASKB 0x07							//!< Mask used to select the LOGB least significant bits
//#define MASKB 0xFFFFFFE0

#define MASKSZ 9							//!< Number of elements in __mask
static const NODETYPE __mask[MASKSZ] = { //!< Array of masks. Entry \c i deletes the \c i least significant bits.
		0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80, 0x00 };

#define NODECOUNTER(w) __builtin_popcount(w)						//!< Builtin function: Returns the number of 1-bits in \c w.
#define NODELEAST(w) (__builtin_ffs(w)-1)							//!< Builtin function: Returns the index of the least significant 1-bit of \c w, or if \c w is zero, returns \c -1.
#define NODENEXTLEAST(w, i) (__builtin_ffs((w) & __mask[i + 1])-1)	//!< Builtin function: Returns the index of the least significant 1-bit of \c w greater than \c i, or if \c w is zero, returns \c -1.
#define NODEMOST(i) (BSIZE-__builtin_clz(i)-1)						//!< Builtin function: Returns the index of the most significant 1-bit of \c w, or if \c w is zero, returns \c -1.
#define NODEPREVMOST(w, i) (BSIZE-__builtin_clz((w) & ~__mask[i])-1)	//!< Builtin function: Returns the index of the most significant 1-bit of \c w smaller than \c i, or if \c w is zero, returns \c -1.
#endif

#define NELEM(i) ((i) << LOGB)								//!< Smallest element in the entry \c i of the bitmap.
#define NODEIDX(i) ((i) >> LOGB)							//!< Node index in the bitmap of element \c i.
#define IDXINNODE(i) ((i) & MASKB)							//!< Element index in the corresponding node of the bitmap.
#define ISINNODE(w, i) ((w) & (ONE << (i)))					//!< Returns a node set to a non-zero value if the bit of index \c i in node \c w is a 1-bit; otherwise a node set to \c 0.
#define ISINSET(T, i) ISINNODE(T[NODEIDX(i)], IDXINNODE(i))	//!< Returns a node set to a non-zero value if the element \c i is in the bitmap \c T; otherwise a node set to \c 0.
#define DELFROMNODE(w, i) ((w) & ~(ONE << (i)))				//!< Deletes bit \c i from node \c w.
#define RETAINLEAST(w, i) ((w) & (NODEMAX >> (BSIZE-(i)))) 	//!< Retains \c i least significant elements of node \c w.
#define ADDTONODE(w, i) ((w) | (ONE << (i)))				//!< Adds bit \c i to node \c w.
#define ADDALL(R, n) memset(R, 0xFF, ((n) << LOGW))			//!< Adds all elements to bitmap \c R.
#define DELALL(R, n) memset(R, 0, ((n) << LOGW))			//!< Deletes all elements from bitmap \c R.
#define COPYALL(R, S, n) memcpy(R, S, ((n) << LOGW))		//!< Copy \c n nodes from bitmap \c S to bitmap \c R.
/*!
 * \fn int cardOfSet(NODETYPE * bmvec, int from, int to)
 * \brief Determines the number of elements in the specified nodes of a bitmap.
 *
 * \param bmvec Bitmap.
 * \param from First node to consider.
 * \param to One plus the last node to consider.
 *
 * \return The number of elements in the nodes indexed \c from to \c to \c - \c 1 of the bitmap \c bmvec.
 */
//int cardOfSet(NODETYPE * bmvec, int from, int to);
static inline int cardOfSet(NODETYPE * bmvec, int from, int to) {
	int node, ret = 0;
	for (node = from; node < to; node++)
		ret += NODECOUNTER(bmvec[node]);
	return ret;
}

/*!
 * \fn void copyAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to)
 * \brief Copy nodes between specified bitmaps.
 *
 * \param bmvec Nodes are copied to this bitmap.
 * \param abmvec Nodes are copied from this bitmap.
 * \param from First node to be copied.
 * \param to One plus the last node to be copied.
 */
//static void copyAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to);
static inline void copyAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to) {
	memcpy(bmvec+from, abmvec+from, (to-from) << LOGW);
}

/*!
 * \fn void addAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to)
 * \brief Add elements between specified bitmaps.
 *
 * This function performs a logic \c OR operation of the specified nodes.
 *
 * \param bmvec Elements are added to this bitmap.
 * \param abmvec Elements of this bitmap are added.
 * \param from First node whose elements are added.
 * \param to One plus the last node whose elements are added.
 */
//static void	addAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to);
static inline void addAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to) {
	int node;
#ifdef _SSE_
#ifdef _ARCH32_
	if (to & 0x11)
		to = (to + 4) & __mask[3];
	for (node = from & __mask[3]; node < to; node = node+4)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_or_si128 (*((__m128i *) (bmvec+node)), *((__m128i *) (abmvec+node))));
#elif _ARCH64_
	if (to & 0x1)
		to++;
	for (node = from & __mask[1]; node < to; node = node+2)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_or_si128 (*((__m128i *) (bmvec+node)), *((__m128i *) (abmvec+node))));
#endif
#else
	for (node = from; node < to; node++)
		bmvec[node] |= abmvec[node];
#endif
}

/*!
 * \fn void removeAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to)
 * \brief Remove elements between specified bitmaps.
 *
 * This function performs a logic \c AND operation of the specified nodes from one bitmap with the negation of nodes from the other bitmap.
 *
 * \param bmvec Elements of this bitmap are removed.
 * \param abmvec Elements are removed from this bitmap.
 * \param from First node whose elements are removed.
 * \param to One plus the last node whose elements are removed.
 */
//static void removeAll(NODETYPE * bmvec, NODETYPE * rbmvec, int from, int to);
static inline void removeAll(NODETYPE * bmvec, NODETYPE * rbmvec, int from,	int to) {
	int node;
#ifdef _SSE_
#ifdef _ARCH32_
	if (to & 0x11)
		to = (to + 4) & __mask[3];
	for (node = from & __mask[3]; node < to; node = node+4)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_andnot_si128 (*((__m128i *) (rbmvec+node)), *((__m128i *) (bmvec+node))));
#elif _ARCH64_
	if (to & 0x1)
		to++;
	for (node = from & __mask[1]; node < to; node = node+2)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_andnot_si128 (*((__m128i *) (rbmvec+node)), *((__m128i *) (bmvec+node))));
#endif
#else
	for (node = from; node < to; node++)
		bmvec[node] &= ~rbmvec[node];
#endif
}

/*!
 * \fn void retainAll(NODETYPE * bmvec, NODETYPE * abmvec, int from, int to)
 * \brief Intersection of bitmaps with the result in one of them.
 *
 * This function performs a logic \c AND operation of the specified nodes.
 *
 * \param bmvec Elements of this bitmap are removed.
 * \param abmvec Elements are removed from this bitmap.
 * \param from First node whose elements are removed.
 * \param to One plus the last node whose elements are removed.
 */
//static void retainAll(NODETYPE * bmvec, NODETYPE * rbmvec, int from, int to);
static inline void retainAll(NODETYPE * bmvec, NODETYPE * rbmvec, int from, int to) {
	int node;
#ifdef _SSE_
#ifdef _ARCH32_
	if (to & 0x11)
		to = (to + 4) & __mask[3];
	for (node = from & __mask[3]; node < to; node = node+4)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_and_si128 (*((__m128i *) (bmvec+node)), *((__m128i *) (rbmvec+node))));
#elif _ARCH64_
	if (to & 0x1)
		to++;
	for (node = from & __mask[1]; node < to; node = node+2)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_and_si128 (*((__m128i *) (bmvec+node)), *((__m128i *) (rbmvec+node))));
#endif
#else
	for (node = from; node < to; node++)
		bmvec[node] &= rbmvec[node];
#endif
}

/*!
 * \fn void intersectOf(NODETYPE * bmvec, NODETYPE * abmvec, NODETYPE * bbmvec, int from, int to)
 * \brief Intersection of bitmaps with the result in a third bitmap.
 *
 * This function performs a logic \c AND operation of the specified nodes.
 *
 * \param bmvec Result bitmap
 * \param abmvec Operand bitmap
 * \param bbmvec Operand bitmap
 * \param from First node for the intersection.
 * \param to One plus the last node for the intersection.
 */
//static void intersectOf(NODETYPE * bmvec, NODETYPE * abmvec, NODETYPE * bbmvec, int from, int to);
static inline void intersectOf(NODETYPE * bmvec, NODETYPE * abmvec,	NODETYPE * bbmvec, int from, int to) {
	int node;
#ifdef _SSE_
#ifdef _ARCH32_
	if (to & 0x11)
		to = (to + 4) & __mask[3];
	for (node = from & __mask[3]; node < to; node = node+4)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_and_si128 (*((__m128i *) (abmvec+node)), *((__m128i *) (bbmvec+node))));
#elif _ARCH64_
	if (to & 0x1)
		to++;
	for (node = from & __mask[1]; node < to; node = node+2)
		_mm_store_si128 ((__m128i *) (bmvec+node), _mm_and_si128 (*((__m128i *) (abmvec+node)), *((__m128i *) (bbmvec+node))));
#endif
#else
	for (node = from; node < to; node++)
		bmvec[node] = abmvec[node] & bbmvec[node];
#endif
}

/*!
 * \fn int minNode(NODETYPE * bm, int i, size_t nnodes)
 * \brief Non-zero node with smallest index of the specified bitmap.
 *
 * \param bm Bitmap
 * \param i First node.
 * \param nnodes One plus last node.
 *
 * \return The smallest index between \c i and \c nnodes \c - \c 1 of a non-zero node in the specified bitmap. If all nodes are zero, then
 * returns \c nnodes.
 */
//static int minNode(NODETYPE * bm, int i, size_t nnodes);
static inline int minNode(NODETYPE * bm, int i, size_t nnodes) {
	while (i < nnodes && !bm[i])
		i++;
	return i;
}

/*!
 * \fn int maxNode(NODETYPE * bm, int i, int mini)
 * \brief Non-zero node with greatest index of the specified bitmap.
 *
 * \param bm Bitmap
 * \param i Last node.
 * \param mini First node.
 *
 * \return The greatest index between \c mini and \c i of a non-zero node in the specified bitmap. If all nodes are zero, then
 * returns \c i \c - \c 1.
 */
//static int maxNode(NODETYPE * bm, int i, int mini);
static inline int maxNode(NODETYPE * bm, int i, int mini) {
	while (i >= mini && !bm[i])
		i--;
	return i;
}

static inline void printSetNodes(NODETYPE * s, int from, int to) {
	int node;

#ifdef _ARCH32_
#define FORMX " %lx"
#elif _ARCH64_
#define FORMX " %llx"
#else
#define FORMX " %x"
#endif

	printf("SET: [");
	for (node = from; node < to; node++)
		printf(FORMX, s[node]);
	printf("]\n");
}

#endif /* BITMAP_H_ */
